---
id: 二叉树
title: 二叉树(binary tree)
---

import tree1 from "../img/2tree.jpg";

- 定义：二叉树是树的一种特殊形式。顾名思义，这种树的每个节点最多有 2 个孩子节点（也可以只有 1 个或者为空）。

### 二叉树的两种特殊形式

- 满二叉树
  - 所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上
- 完全二叉树
  - 对一个有 n 个节点的二叉树，按层级顺序编号，则所有节点的编号为从 1 到 n。如 果这个树所有节点和同样深度的满二叉树的编号为从 1 到 n 的节点位置相同，则这个 二叉树为完全二叉树。
- 两者区别
  - 完全二叉树的条件没有满二叉树那么苛刻:满二叉树要求所有分支都是满的;而完全二叉树只需保证最后一个节点之前的节点都齐全即可。
  - 二叉树可以链式存储结构和数组来表达呢?

### 二叉树的应用

二叉树包含许多特殊的形式，每一种形式都有自己的作用，但是其最主要的应用还在于进行查找操作和维持相对顺序这两个方面

- 查找  
  二叉树的树形结构使它很适合扮演索引的角色。这里介绍一种特殊的二叉树:二叉查找树 BST(binary search tree)。其主要作用是进行查找操作。

  - 二叉查找树在二叉树的基础上增加了以下条件。
    - 左子树上所有节点的值均小于根节点的值，右子树不为空，则右子树上所有节点的值均大于根节点的值。
  - 一个节点分布相对均衡的二叉查找树，如果节点总数是 n，那么搜索节点的时间复杂度就是 O(logn)，和树的深度是一样的。

- 维持相对顺序  
  二叉查找树要求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性。因此二叉查找树还有另一个名字——二叉排序树(binary sort tree)。
  - 致命问题  
    二叉树的平衡问题，二叉查找树中依次插入 9、8、7、6、5、4，看看会出现什么结果。
  - 解决办法  
    二叉树的自平衡了。二叉树自平衡的方式有多种，如红黑树、AVL 树、树堆等。

### 二叉树的实现

#### python 实现

- #### 添加节点

  - put 方法

    ```python
        # 首先看 BST 是否为空，如果一个节点都没有，那么 key 成为根节点 root,
        # 否则，就调用一个递归函数\_put(key, val,root)来放置 key

        def put(self, key, val):
            if self.root:
                self._put(key,val,self.root);
            else:
                self.root= TreeNode(key,val);
            self.size+=1;
    ```

  - \_put 辅助方法

    ```python
    # 如果 key 比 currentNode 小，那么\_put 到左子树。如果没有左子树，那么 key 就成为左子节点
    # 如果 key 比 currentNode 大，那么\_put 到右子树。如果没有右子树，那么 key 就成为右子节点

    def _put(self, key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild); # 递归左子树
            else:
                currentNode.leftChild = TreeNode(key,val,parent=currentNode);
        else:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild);# 递归右子树
            else:
                currentNode.rightChild = TreeNode(key,val,parent=currentNode);

    ```

#### 查找节点

- ```python
             # 在树中找到 key 所在的节点取到 payload
             def get(self, key):
                 if self.root:
                     res = self._get(key, self.root);
                     if res:
                         return res;
                     else:
                         return None;
                 else:
                     return None;

             def _get(self, key, currenNode):
                 if not currenNode:
                     return None;
                 elif currenNode.key == key:
                     return currenNode;
                 elif key < currenNode.key:
                     return self._get(key,currenNode.leftChild);
                 else:
                     return self._get(key, currenNode.rightChild);

         ```

#### 删除节点

- delete 方法

  ```python
       # 用_get 找到要删除的节点，然后调用 remove 来删除，找不到则提示错误
       # 在 delete 中，最复杂的是找到 key 对应的节点之后的 remove 节点方法！

      def delete(self, key):
          if self.size >1:
              nodeToRemove = self._get(key, self.key);
              if nodeToRemove:
                  self.remove(nodeToRemove);
                  self.size = self.size - 1;
              else:
                  raise KeyError('Error: key not in tree');
          elif self.size == 1 and self.root.key == key:
              self.root = None;
              self.size = self.size -1;
          else:
              raise KeyError('Error: key not in tree');
  ```

- remove 方法

  ```python
      def remove(self, currentNode):

          # if 第1种情况：叶子节点
          # else if 第2种情形 有2个子节点
          # else 第3种情形：被删节点有1个子节点。解决：将这个唯一的子节点上移，替换掉被删节点的位置
          if currentNode.isLeaf():
              if currentNode == currentNode.parent.leftChild: # 判断一下是左子节点还右子节点
                  currentNode.parent.leftChild = None;
              else:
                  currentNode.parent.rightChild = None;
          elif currentNode.hasBothChildren():  # interior
              succ = currentNode.findSuccessor()
              # succ.spliceOut()
              currentNode.key = succ.key
              currentNode.payload = succ.payload
          else: # this node has one child
              if currentNode.hasLeftChild():
                  if currentNode.isLeftChild(): # 左子节点删除
                      currentNode.leftChild.parent = currentNode.parent;
                      currentNode.parent.leftChild = currentNode.leftChild;
                  elif currentNode.isRightChild(): # 右子节点删除
                      currentNode.leftChild.parent = currentNode.parent;
                      currentNode.parent.rightChild = currentNode.leftChild;
                  else: # 根节点删除
                      currentNode.replaceNodeData(currentNode.leftChild.key,
                                              currentNode.leftChild.payload,
                                              currentNode.leftChild.leftChild,
                                              currentNode.leftChild.rightChild)
              else:
                  if currentNode.isLeftChild(): # 左子节点删除
                      currentNode.rightChild.parent = currentNode.parent;
                      currentNode.parent.leftChild = currentNode.rightChild;
                  elif currentNode.isRightChild(): # 右子节点删除
                      currentNode.rightChild.parent = currentNode.parent;
                      currentNode.parent.rightChild = currentNode.rightChild;
                  else:  # 根节点删除
                      currentNode.replaceNodeData(currentNode.rightChild.key,
                                              currentNode.rightChild.payload,
                                              currentNode.rightChild.leftChild,
                                              currentNode.rightChild.rightChild)
  ```

- TreeNode 类：寻找后继节点

  ```python
        def findSuccessor(self): # 寻找后继节点
            succ = None
            if self.hasRightChild():
                succ = self.rightChild.findMin()
            else:
                if self.parent:
                    if self.isLeftChild():
                        succ = self.parent
                    else:
                        self.parent.rightChild = None
                        succ = self.parent.findSuccessor()
                        self.parent.rightChild = self
            return succ

        def findMin(self):
            current = self
            while current.hasLeftChild():
                current = current.leftChild
            return current

  ```

- TreeNode 类：摘出节点 spliceOut()

```python

    def spliceOut(self): # 摘出节点spliceOut()
        if self.isLeaf():
            if self.isLeftChild():
                self.parent.leftChild = None
            else:
                self.parent.rightChild = None
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                if self.isLeftChild():
                    self.parent.leftChild = self.leftChild
                else:
                    self.parent.rightChild = self.leftChild
                self.leftChild.parent = self.parent
            else:
                if self.isLeftChild():
                    self.parent.leftChild = self.rightChild
                else:
                    self.parent.rightChild = self.rightChild
                self.rightChild.parent = self.parent
```

#### 索引操作

- \_\_setitem\_\_

  - 实现 bst['xx'] = 123
  - ```python
       def __setitem__(self, key, value):
           self.put(key,value);
    ```

- \_\_getitem\_\_

  - 实现 val= bst['xx']
  - ```python
        def __getitem__(self, key):
            return self.get(key);
    ```

- \_\_delitem\_\_

  - 实现 del bst['xx']这样的语句操作
  - ```python
      def __delitem__(self, key):
        self.delete(key);
    ```

#### 判断是否存在

- \_\_contains\_\_
  - 实现'PKU' in myZipTree 的归属判断运算符 in
  - ```python
        def __contains__(self, key):
        if self._get(key, self.root):
            return True;
        else:
            return False;
    ```

#### 迭代器的实现

- BST 类中的\_\_iter\_\_方法直接调用了 TreeNode 中的同名方法

```python
     def __iter__(self):
        if self:
            if self.hasLeftChild():
                for elem in self.leftChild:
                    yield elem;
            yield self.key;
            if self.hasRightChild():
                for elem in self.rightChild:
                    yield elem;
```

#### 完整代码

```python


class TreeNode:
    def __init__(self, key, val, left=None,right=None, parent=None):
        self.key = key;
        self.payload = val;
        self.leftChild = left;
        self.rightChild = right;
        self.parent = parent;

    # 迭代器函数中用了for迭代，实际上是递归函数
    # yield是对每次迭代的返回值中序遍历的迭代
    def __iter__(self):
        if self:
            if self.hasLeftChild():
                for elem in self.leftChild:
                    yield elem;
            yield self.key;
            if self.hasRightChild():
                for elem in self.rightChild:
                    yield elem;
    def hasLeftChild(self):
        return self.leftChild;

    def hasRightChild(self):
        return self.rightChild;

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self;

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self;

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not(self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild;
    def hasBothChildren(self):
        return self.rightChild and self.leftChild;

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key;
        self.payload = value;
        self.leftChild = lc;
        self.rightChild = rc;
        if self.hasLeftChild():
            self.leftChild.parent = self;
        if self.hasRightChild():
            self.rightChild.parent = self;

    def findSuccessor(self): # 寻找后继节点
        succ = None
        if self.hasRightChild():
            succ = self.rightChild
            # succ = self.rightChild.findMin()
        else:
            if self.parent:
                if self.isLeftChild():
                    succ = self.parent
                else:
                    self.parent.rightChild = None
                    succ = self.parent.findSuccessor()
                    self.parent.rightChild = self
        return succ

    # def findMin(self):
    #     current = self
    #     while current.hasLeftChild():
    #         current = current.leftChild
    #     return current

    def spliceOut(self): # 摘出节点spliceOut()
        if self.isLeaf():
            if self.isLeftChild():
                self.parent.leftChild = None
            else:
                self.parent.rightChild = None
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                if self.isLeftChild():
                    self.parent.leftChild = self.leftChild
                else:
                    self.parent.rightChild = self.leftChild
                self.leftChild.parent = self.parent
            else:
                if self.isLeftChild():
                    self.parent.leftChild = self.rightChild
                else:
                    self.parent.rightChild = self.rightChild
                self.rightChild.parent = self.parent


class BinarySearchTree:
    def __init__(self):
        self.root = None;
        self.size = 0;
    def length(self):
        return self.size;

    def __len__(self):
        return self.size;

    def __iter__(self):
        return self.root.__iter__();


    def put(self, key, val):
        if self.root:
            self._put(key,val,self.root);
        else:
            self.root= TreeNode(key,val);
        self.size+=1;

    def _put(self, key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild); # 递归左子树
            else:
                currentNode.leftChild = TreeNode(key,val,parent=currentNode);
        else:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild);# 递归右子树
            else:
                currentNode.rightChild = TreeNode(key,val,parent=currentNode);



    def get(self, key):
        if self.root:
            res = self._get(key, self.root);
            if res:
                return res;
            else:
                return None;
        else:
            return None;

    def _get(self, key, currentNode):
        if not currentNode:
            return None;
        elif currentNode.key == key:
            return currentNode;
        elif key < currentNode.key:
            return self._get(key,currentNode.leftChild);
        else:
            return self._get(key, currentNode.rightChild);

    def __setitem__(self, key, value):
        self.put(key,value);

    # 实现val= myZipTree['PKU']
    def __getitem__(self, key):
        return self.get(key);

    def __delitem__(self, key):
        self.delete(key);

    # 实现'PKU' in myZipTree的归属判断运算符in
    def __contains__(self, key):
        if self._get(key, self.root):
            return True;
        else:
            return False;

    #用_get找到要删除的节点，然后调用remove来删除，找不到则提示错误
    def delete(self, key):
        if self.size > 1:
            nodeToRemove = self._get(key, self.root);
            if nodeToRemove:
                self.remove(nodeToRemove);
                self.size -= 1;
            else:
                raise KeyError('Error: key not in tree');
        elif self.size == 1 and self.root.key == key: # 只有一个节点那就和根节点比较一下
            self.root = None;
            self.size -= 1;
        else:
            raise KeyError('Error: key not in tree');



    # 这个节点没有子节点
    # 这个节点有1个子节点
    # 这个节点有2个子节点
    def remove(self, currentNode):

        # if 第1种情况：叶子节点
        # else if 第2种情形 有2个子节点
        # else 第3种情形：被删节点有1个子节点。解决：将这个唯一的子节点上移，替换掉被删节点的位置
        if currentNode.isLeaf():
            if currentNode == currentNode.parent.leftChild: # 判断一下是左子节点还右子节点
                currentNode.parent.leftChild = None;
            else:
                currentNode.parent.rightChild = None;
        elif currentNode.hasBothChildren():  # interior
            succ = currentNode.findSuccessor()
            # succ.spliceOut()
            currentNode.key = succ.key
            currentNode.payload = succ.payload
        else: # this node has one child
            if currentNode.hasLeftChild():
                if currentNode.isLeftChild(): # 左子节点删除
                    currentNode.leftChild.parent = currentNode.parent;
                    currentNode.parent.leftChild = currentNode.leftChild;
                elif currentNode.isRightChild(): # 右子节点删除
                    currentNode.leftChild.parent = currentNode.parent;
                    currentNode.parent.rightChild = currentNode.leftChild;
                else: # 根节点删除
                    currentNode.replaceNodeData(currentNode.leftChild.key,
                                               currentNode.leftChild.payload,
                                               currentNode.leftChild.leftChild,
                                               currentNode.leftChild.rightChild)
            else:
                if currentNode.isLeftChild(): # 左子节点删除
                    currentNode.rightChild.parent = currentNode.parent;
                    currentNode.parent.leftChild = currentNode.rightChild;
                elif currentNode.isRightChild(): # 右子节点删除
                    currentNode.rightChild.parent = currentNode.parent;
                    currentNode.parent.rightChild = currentNode.rightChild;
                else:  # 根节点删除
                    currentNode.replaceNodeData(currentNode.rightChild.key,
                                               currentNode.rightChild.payload,
                                               currentNode.rightChild.leftChild,
                                               currentNode.rightChild.rightChild)


# 按间距中的绿色按钮以运行脚本。
if __name__ == '__main__':
    bst = BinarySearchTree();

    # 添加节点
    # bst.put(11,'')
    # print('size：',bst.size, '值：', bst.root.key)
    # bst.put(22,'')
    # print('size：',bst.size, '值：', bst.root.rightChild.key)
    # bst.put(21, '')
    # print('size：',bst.size, '值：', bst.root.rightChild.leftChild.key)

    # 删除节点

    # 第1种情况删除叶子节点
    # bst.delete(21)
    # print('size：',bst.size, '值：', bst.root.rightChild.key)

    # 第2种情况删除只有1个子节点的
    # bst.delete(22)
    # print('size：',bst.size, '值：', bst.root.rightChild.key)

    # 第3种情况删除有2个子节点的
    # bst.put(23, '')
    # bst.delete(22)
    # print('size：', bst.size, '值：', bst.root.rightChild.key)

    # 索引操作
    # bst.put('a',11)
    # bst.put('b',12)
    #
    # # setitem
    # bst['c'] = 13
    #
    # # getitem
    # print(bst['c'].payload)
    #
    # #delitem
    # del bst['c']
    # print(bst['c'].payload)
    #
    # # 判断是否存在
    # print('c' in bst)



# 访问 https://www.jetbrains.com/help/pycharm/ 获取 PyCharm 帮助


```

### 二叉树遍历方式

- 从节点之间位置关系的角度来看分为 4 种。
  1. 前序遍历。
  2. 中序遍历。
  3. 后序遍历。
  4. 层序遍历。
- 从更宏观的角度来看，二叉树的遍历归结为两大类。
  1. 深度优先遍历(前序遍历、中序遍历、后序遍历)。
  2. 广度优先遍历(层序遍历)。

### 二叉树存在的问题

- 容易处于左倾或右倾的状态（复杂度也从 O(logn) 退化成 On）

<img
  src={tree1}
  style={{ width: "400px" }}
  alt="二叉树存在的问题"
  title="二叉树存在的问题"
/>

<!--


```java
public class Find {

    public static void main(String[] args) {

        Integer[] list = {1,9,4,9,1,0,0,1};

        int res = Find.index(list, 0);
        System.out.println(res); // 结果是5
    }


    public static <E> int index(E[] list, E target){
        for(int i = 0; i< list.length; i++)
            if(list[i].equals(target))
                return i;

        return -1;
    }

}
````

```js
class Find {
  static index(list, target) {
    for (let i = 0; i < list.length; i++) if (list[i] === target) return i;

    return -1;
  }
}

const list = [1, 9, 4, 9, 1, 0, 0, 1];
const res = Find.index(list, 0);
console.log(res);
```

## 优先队列

优先队列分为最大优先队列和最小优先队列。
在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是
基于最大堆实现的。
在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是
基于最小堆实现的。 -->
